package offer.offer03;

import java.util.HashMap;
import java.util.Map;

/**
 * 非常漂亮的位运算的题目。
 * bitmap对于integer来说, 需要2^32位来表示他, 也就是相当于2^32 / 32 , 2^27 个int的内存,
 * 这是非常大的, 所以数据少的话, bitmap完全没必要。
 */
public class S56数组中数字出现的次数II {
    /**
     * 13, 虽然这么写不合适, 不过可以学习一下map
     * map怎么遍历效率高?
     */
    public int singleNumber(int[] nums) {
        Map<Integer, Integer> map = new HashMap<>();
        for(int i: nums){
            map.put(i, map.containsKey(i)? map.get(i) + 1: 1);
        }
        for(Integer i: map.keySet()){
            if(map.get(i) == 1)
                return i;
        }
        return -1;
    }
    /**
     * 直接看题解吧, 我已经呆了。
     * 如下所示，考虑数字的二进制形式，对于出现三次的数字，各 二进制位 出现的次数都是 33 的倍数。
     * 因此，统计所有数字的各二进制位中 11 的出现次数，并对 33 求余，结果则为只出现一次的数字
     */
    public int singleNumber2(int[] nums) {
        int ones = 0, twos = 0;
        for(int num : nums){
            ones = ones ^ num & ~twos;
            twos = twos ^ num & ~ones;
        }
        return ones;
    }

    /**
     * 上面的方法的正常人版本
     */
    public int singleNumber3(int[] nums) {
        int[] counts = new int[32];
        for(int num : nums) {
            // 逐个加上num的每一位的数据
            for(int j = 0; j < 32; j++) {
                counts[j] += num & 1;
                num >>>= 1;
            }
        }
        // 由高位到低位, 把结果加起来
        int res = 0, m = 3;
        for(int i = 0; i < 32; i++) {
            res <<= 1;
            res |= counts[31 - i] % m;
        }
        return res;
    }
}
